class Solution {
public:
    int getCommon(vector<int>& nums1, vector<int>& nums2) {
        int n1 = 0, n2 = 0;
        while (n1 < nums1.size() && n2 < nums2.size()) {
            if (nums1[n1] > nums2[n2]) {
                n2++;
            } else if (nums1[n1] < nums2[n2])
                n1++;
            else
                return nums1[n1];
        }
         return -1;
    }
};
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int right = m + n - 1;
        m--,n--;
        while (right >= 0) {
            if (n < 0 || (m >= 0 && nums1[m] > nums2[n])) {
                nums1[right--] = nums1[m--];
            } else {
                nums1[right--] = nums2[n--];
            }
        }
    }
};
class Solution {
public:
    vector<vector<int>> mergeArrays(vector<vector<int>>& nums1,
                                    vector<vector<int>>& nums2) {
        int n1 = nums1.size(), n2 = nums2.size();
        int a = 0, b = 0;
        vector<vector<int>> ret;
        while (a < n1 || b < n2) {
            if (b == n2 || (a < n1 && nums1[a][0] < nums2[b][0])) {
                ret.push_back(nums1[a++]);
            } else if (a == n1 || (b < n2 && nums1[a][0] > nums2[b][0])) {
                ret.push_back(nums2[b++]);
            } else {
                ret.push_back({nums1[a][0], nums1[a++][1] + nums2[b++][1]});
            }
        }
        return ret;
    }
};
const int N = 1e9 + 7;
class Solution {
public:
    int breakfastNumber(vector<int>& staple, vector<int>& drinks, int x) {
        sort(staple.begin(), staple.end());
        sort(drinks.begin(), drinks.end());
        int left1 = 0, n1 = staple.size(), n2 = drinks.size();
        int right2 = n2 - 1, ans = 0;
        while (left1 < n1) {
            while (right2 >= 0 && staple[left1] + drinks[right2] > x) {
                right2--;
            }
            if (right2 == -1)
                break;
            ans = (ans + right2 + 1) % N;
            left1++;
        }
        return ans;
    }
};
class Solution {
public:
    int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
        sort(arr1.begin(), arr1.end());
        sort(arr2.begin(), arr2.end());
        int n1 = arr1.size(), n2 = arr2.size();
        int left = 0, right = 0, ans = 0;
        for (int i = 0; i < n1; i++) {
            while (left < n2 && arr2[left] < arr1[i] - d)
                left++;
            if (left == n2 || arr2[left] > arr1[i] + d) {
                ans++;
            }
        }
        return ans;
    }
};
class Solution {
public:
    int maxDistance(vector<int>& nums1, vector<int>& nums2) {
        int n1 = nums1.size(), n2 = nums2.size();
        int left1 = 0, left2 = 0, ans = 0;
        while (left1 < n1 && left1 < n2) {
            while (left2 < n2 && nums1[left1] <= nums2[left2]) {
                left2++;
            }
            ans = max(ans,left2 - left1 - 1);
            left1++;
        }
        return ans;
    }
};
class Solution {
public:
    bool isLongPressedName(string name, string typed) {
        int n1 = name.size(), n2 = typed.size(), a = 0, b = 0;
        while (a <= n1 && b < n2) {
            if (a < n1 && name[a] == typed[b]) {
                a++,b++;
            } else {
                if (a > 0 && name[a - 1] == typed[b])
                    while (b < n2 && name[a - 1] == typed[b]) {
                        b++;
                    }
                else
                    return false;
            }
        }
        return a == n1 && b == n2;
    }
};
class Solution {
public:
    int expressiveWords(string s, vector<string>& words) {
        int n1 = s.size(), n2 = 0, ans = 0;

        for (auto& str : words) {
            n2 = str.size();
            bool t  =true;
            int a1 = 0, a2 = 0, pos1 = 0, pos2 = 0;
            while (pos1 < n1 && pos2 < n2) {
                if (s[pos1] != str[pos2]) {
                    cout << str << ' ' << pos2 << endl;
                    t = false;
                    break;
                }
                pos1++, pos2++, a1++, a2++;
                while (pos1 < n1 && s[pos1] == s[pos1 - 1])
                    a1++, pos1++;
                while (pos2 < n2 && str[pos2] == str[pos2 - 1])
                    a2++, pos2++;
                // cout << pos1 << ' ' << pos2 << endl;
                // cout << a1 << ' ' << a2 << endl;
                // cout << endl;
                if (a1 == a2 || (a1 > a2 && a1 >= 3)) {
                    a1 = 0, a2 = 0;
                    continue;
                } else {
                    t = false;
                    break;
                }
            }
            if(pos1 == n1 && pos2 == n2 && t) {
                //cout << str << endl;
                ans++;
            }
        }
        return ans;
    }
};
class Solution {
public:
    bool canChange(string start, string target) {
        int n1 = start.size(), n2 = target.size();
        int a1 = 0, a2 = 0;
        while (a1 < n1 || a2 < n2) {
            while (a1 < n1 && start[a1] == '_')
                a1++;
            while (a2 < n2 && target[a2] == '_')
                a2++;
            if (a1 < n1 && a2 < n2 && start[a1] == target[a2]) {
                if ((start[a1] == 'L' && a1 >= a2) ||
                    start[a1] == 'R' && a1 <= a2) {
                    a1++, a2++;
                    continue;
                }
            }
            break;
        }
        if (a1 == n1 && a2 == n2)
            return true;
        else
            return false;
    }
};
class Solution {
public:
    bool canTransform(string start, string result) {
        int n1 = start.size(), n2 = result.size();
        int a1 = 0, a2 = 0;
        while (a1 < n1 || a2 < n2) {
            while (a1 < n1 && start[a1] == 'X')
                a1++;
            while (a2 < n2 && result[a2] == 'X')
                a2++;
            if (a1 < n1 && a2 < n2 && start[a1] == result[a2]) {
                if ((start[a1] == 'L' && a1 >= a2) ||
                    start[a1] == 'R' && a1 <= a2) {
                    a1++, a2++;
                    continue;
                }
            }
            break;
        }
        if (a1 == n1 && a2 == n2)
            return true;
        else
            return false;
    }
};
class Solution {
public:
    bool backspaceCompare(string s, string t) {
        stack<int> ss, tt;
        for (auto& c : s) {
            if (c == '#') {
                if (!ss.empty())
                    ss.pop();
            } else
                ss.push(c);
        }
        for (auto& c : t) {
            if (c == '#') {
                if (!tt.empty())
                    tt.pop();
            } else
                tt.push(c);
        }
        if(ss.size() == tt.size()){
            while(!ss.empty()){
                if(ss.top() != tt.top())
                    return false;
                ss.pop(),tt.pop();
            }
            return true;
        }
        return false;
    }
};
class Solution {
public:
    vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList,
                                             vector<vector<int>>& secondList) {
        int left1 = 0, left2 = 0;
        int n1 = firstList.size(), n2 = secondList.size();
        vector<vector<int>> ans;
        while (left1 < n1) {
            while (left2 < n2 && firstList[left1][0] > secondList[left2][1])
                left2++;
            if (left2 == n2)
                break;
            while (left2 < n2 && firstList[left1][1] >= secondList[left2][0]) {
                int left = max(firstList[left1][0], secondList[left2][0]);
                int right = min(firstList[left1][1], secondList[left2][1]);
                // cout << left << ' ' << right << endl;
                ans.push_back({left, right});
                if(firstList[left1][1] > secondList[left2][1])
                    left2++;
                else
                    break;
            }
            left1++;
        }
        return ans;
    }
};
class Solution {
public:
    int smallestDifference(vector<int>& a, vector<int>& b) {
        sort(a.begin(), a.end());
        sort(b.begin(), b.end());
        long long left1 = 0, left2 = 0,n1 = a.size(), n2 = b.size(),
                  ans = 2147483648;
        while (left1 < n1 && left2 < n2) {
            // cout << a[left1] <<' ' << b[left2] << endl;
            if (ans <= abs((long long)a[left1] - (long long)b[left2])) {
                if (a[left1] < b[left2]) {
                    left1++;
                } else {
                    left2++;
                }
            } else {
                ans = abs(a[left1] - b[left2]);
            }
            if (ans == 0)
                return 0;
        }
        return ans;
    }
};
class Solution {
public:
    int maxSum(vector<int>& nums1, vector<int>& nums2) {
        int n = 1e9 + 7;
        nums1.push_back(n);
        nums2.push_back(n);
        long long n1 = nums1.size(), n2 = nums2.size(), right1 = 0, right2 = 0;
        long long sumleft1 = 0, sumleft2 = 0, sumright1 = 0, sumright2 = 0,
                  ans = 0;
        while (right1 < n1) {
            while (right2 < n2 && nums1[right1] > nums2[right2]) {
                sumright2 = (sumright2 + nums2[right2++]);
            }
            if (nums1[right1] == nums2[right2]) {
                ans += max(sumright1 - sumleft1, sumright2 - sumleft2);
                sumleft1 = sumright1, sumleft2 = sumright2;
            }
            sumright1 = (sumright1 + nums1[right1++]);
        }
        return ans % n;
    }
};